#include <stdio.h>
int climbStairs(int n) 
{
    
    if(n <= 2)
    return n;

    int *dp = (int *)malloc((n + 1) * sizeof(int));
    dp[1] = 1;
    dp[2] = 2;

    for(int i = 3; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
    free(dp);




    // if(n == 1 || n == 2)
    //     return n;
    // else
    // {
    //     return climbStairs(n-1)+climbStairs(n-2);
    // }
}

int main()
{
    int n = 5;
    printf("%d\n",climbStairs(n));
}